//https://leetcode.cn/problems/all-possible-full-binary-trees/?envType=daily-question&envId=2024-04-02


class Solution {
public:
    vector<TreeNode*> allPossibleFBT(int n) {
        if (n == 1) return vector<TreeNode*>(1, new TreeNode(0));
        n--;
        vector<TreeNode *> ret;
        for (int l = 1; l < n; l += 2) {
            vector<TreeNode*> lrs = allPossibleFBT(l);
            vector<TreeNode*> rrs = allPossibleFBT(n-l);
            for (auto lr: lrs)
            for (auto rr: rrs) {
                ret.push_back(new TreeNode(0, lr, rr));
            }
        }
        return ret;
    }
};